Copositivity Detection of Tensors: Theory and Algorithm

A symmetric tensor is called copositive if it generates a multivariate form taking nonnegative values over the nonnegative orthant. Copositive tensors have found important applications in polynomial optimization, tensor complementarity problems and vacuum stability of a general scalar potential. In this paper, we consider copositivity detection of tensors from both theoretical and computational points of view. After giving several necessary conditions for copositive tensors, we propose several new criteria for copositive tensors based on the representation of the multivariate form in barycentric coordinates with respect to the standard simplex and simplicial partitions. It is verified that, as the partition gets finer and finer, the concerned conditions eventually capture all strictly copositive tensors. Based on the obtained theoretical results with the help of simplicial partitions, we propose a numerical method to judge whether a tensor is copositive or not. The preliminary numerical results confirm our theoretical findings.     

Potential operators associated with Hankel and Hankel-Dunkl transforms

We study Riesz and Bessel potentials in the settings of Hankel transform, modified Hankel transform and Hankel-Dunkl transform. We prove sharp or qualitatively sharp pointwise estimates of the corresponding potential kernels. Then we characterize those 1 ≤ p, q≤∞, for which the potential operators satisfy L ^p -L ^q estimates. In case of the Riesz potentials, we also characterize those 1 ≤ p, q ≤ ∞, for which two-weight L ^p -L ^q estimates, with power weights involved, hold. As a special case of our results, we obtain a full characterization of two power-weight L ^p -L ^q bounds for the classical Riesz potentials in the radial case. This complements an old result of Rubin and its recent reinvestigations by De Nápoli, Drelichman and Durán, and Duoandikoetxea.     

Generalised continuation by means of right limits

Several theories have been proposed to generalise the concept of analytic continuation to holomorphic functions of the disc for which the circle is a natural boundary. Elaborating on Breuer-Simon’s work on right limits of power series, Baladi-Marmi-Sauzin recently introduced the notion of renascent right limit and rrl-continuation. We discuss a few examples and consider particularly the classical example of Poincaré simple pole series in this light. These functions are represented in the disc as series of infinitely many simple poles located on the circle; they appear, for instance, in small divisor problems in dynamics. We prove that any such function admits a unique rrl-continuation, which coincides with the function obtained outside the disc by summing the simple pole expansion. We also discuss the relation with monogenic regularity in the sense of Borel.     

Approximate Euclidean Steiner Trees

An approximate Steiner tree is a Steiner tree on a given set of terminals in Euclidean space such that the angles at the Steiner points are within a specified error from \(120^{\circ }\). This notion arises in numerical approximations of minimum Steiner trees. We investigate the worst-case relative error of the length of an approximate Steiner tree compared to the shortest tree with the same topology. It has been conjectured that this relative error is at most linear in the maximum error at the angles, independent of the number of terminals. We verify this conjecture for the two-dimensional case as long as the maximum angle error is sufficiently small in terms of the number of terminals. In the two-dimensional case we derive a lower bound for the relative error in length. This bound is linear in terms of the maximum angle error when the angle error is sufficiently small in terms of the number of terminals. We find improved estimates of the relative error in length for larger values of the maximum angle error and calculate exact values in the plane for three and four terminals.     

Multi-objective Geometry Optimization of a Gas Cyclone Using Triple-Fidelity Co-Kriging Surrogate Models

Cyclone separators are widely used in a variety of industrial applications. A low-mass loading gas cyclone is characterized by two performance parameters, namely the Euler and Stokes numbers. These parameters are highly sensitive to the geometrical design parameters defining the cyclone. Optimizing the cyclone geometry therefore is a complex problem. Testing a large number of cyclone geometries is impractical due to time constraints. Experimental data and even computational fluid dynamics simulations are time-consuming to perform, with a single simulation or experiment taking several weeks. Simpler analytical models are therefore often used to expedite the design process. However, this comes at the cost of model accuracy. Existing techniques used for cyclone shape optimization in literature do not take multiple fidelities into account. This work combines cheap-to-evaluate well-known mathematical models of cyclones, available data from computational fluid dynamics simulations and experimental data to build a triple-fidelity recursive co-Kriging model. This model can be used as a surrogate with a multi-objective optimization algorithm to identify a Pareto set of a finite number of solutions. The proposed scheme is applied to optimize the cyclone geometry, parametrized by seven design variables.     

Duality Theorems for Separable Convex Programming Without Qualifications

In the research of mathematical programming, duality theorems are essential and important elements. Recently, Lagrange duality theorems for separable convex programming have been studied. Tseng proves that there is no duality gap in Lagrange duality for separable convex programming without any qualifications. In other words, although the infimum value of the primal problem equals to the supremum value of the Lagrange dual problem, Lagrange multiplier does not always exist. Jeyakumar and Li prove that Lagrange multiplier always exists without any qualifications for separable sublinear programming. Furthermore, Jeyakumar and Li introduce a necessary and sufficient constraint qualification for Lagrange duality theorem for separable convex programming. However, separable convex constraints do not always satisfy the constraint qualification, that is, Lagrange duality does not always hold for separable convex programming. In this paper, we study duality theorems for separable convex programming without any qualifications. We show that a separable convex inequality system always satisfies the closed cone constraint qualification for quasiconvex programming and investigate a Lagrange-type duality theorem for separable convex programming. In addition, we introduce a duality theorem and a necessary and sufficient optimality condition for a separable convex programming problem, whose constraints do not satisfy the Slater condition.     

Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions

We investigate how well the graph of a bilinear function \(b{:}\;[0,1]^n\rightarrow \mathbb {R}\) can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number c such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most c times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor c cannot be bounded by a constant independent of n. More precisely, we show that for a random bilinear function b we have asymptotically almost surely \(c\geqslant \sqrt{n}/4\). On the other hand, we prove that \(c\leqslant 600\sqrt{n}\), which improves the linear upper bound proved by Luedtke, Namazifar and Linderoth. In addition, we present an alternative proof for a result of Misener, Smadbeck and Floudas characterizing functions b for which the McCormick relaxation is equal to the convex hull.     

A robust and efficient method for solving point distance problems by homotopy

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables by introducing additional auxiliary variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all “minimal” quadratizations of negative monomials.     

An axiomatic duality framework for the theta body and related convex corners

Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are generalized, including the main equivalent characterizations of the theta function, the theta body of graphs, and the corresponding antiblocking duality relations. Our framework describes several semidefinite and polyhedral relaxations of the stable set polytope of a graph as generalized theta bodies. As a by-product of our approach, we introduce the notion of “Schur Lifting” of cones which is dual to PSD Lifting (more commonly used in SDP relaxations of combinatorial optimization problems) in our axiomatic generalization. We also generalize the notion of complements of graphs to diagonally scaling-invariant polyhedral cones. Finally, we provide a weighted generalization of the copositive formulation of the fractional chromatic number by Dukanovic and Rendl from 2010.